package com.leetcode.algorithm.y22.m06;

/**
 * 518. 零钱兑换 II
 * 
 * https://leetcode.cn/problems/coin-change-2/
 * 
 * @author jie.deng
 *
 */
class Question0518Solution01 {

	public int change(int amount, int[] coins) {
		// 完全背包问题
		// dp[i][j]表示使用前i种硬币凑成金额j的组合数
		int[] dp = new int[amount + 1];
		// 状态初始化
		dp[0] = 1;

		// 状态转移方程
		for (int j = 0; j < coins.length; j++) {
			for (int i = coins[j]; i <= amount; i++) {
				dp[i] += dp[i - coins[j]];
			}
		}

		return dp[amount];
	}

}